package cn.z2huo.leetcode.problem.NO_0005;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
/**
 * 最长回文子串，使用动态规划算法解决
 * @author zyz
 * 给定一个字符串s，找到s中最长的回文子串。你可以假设  s的最大长度为1000。
 * 输入： “babad”
 * 输出： “bab”
 * 注意： “aba”也是一个有效答案。
 */
public class Main {
	
	public String longestPalindrome(String str) {
		// 判断长度为1或者为空字符串的情况
		if(str.length()==1) {
			return str;
		}else if(str.isEmpty() || str=="") {
			return "";
		}
		// 准备工作
		// 初始化一系列变量
		List<String> list = new ArrayList<>();
		int maxLength = 0;
		boolean[][] array = new boolean[str.length()][str.length()];
		// 将数组中所有的位置填充为 false
		for (int i = 0; i < array.length; i++) {
			Arrays.fill(array[i], false);
		}
		// 将数组中对角线的元素设置为true，并将该位置代表的元素添加到结果list中
		// 判断字符串中是否有相邻的两个字符是相同的，如果有添加到结果list中
		// 此for循环可以得出字符串中所有单个字符以及两个字符对称的情况，例如“bb”
		for (int i = 0; i < str.length(); i++) {
			array[i][i] = true;
			list.add(str.substring(i,i+1));
			if (i<str.length()-1 && str.charAt(i)==str.charAt(i+1)) {
				list.add(str.substring(i, i+2));
				array[i][i+1] = true;
				maxLength = 2;
			}
		}
		// 找长度为3及以上的对称子字符串
		for(int len=3; len<=str.length(); len++) {
			for (int j = 0; j <= str.length()-len; j++) {
				int m = j+len-1;
				if(array[j+1][m-1] && str.charAt(j)==str.charAt(m)){
					list.add(str.substring(j,m+1));
					array[j][m] = true;
					maxLength = len;
				}
			}
		}
		pringList(list);
		System.out.println(maxLength);
		printArray(array);
		// 比较器，根据list中string的长度返回长度最长的string元素
		return Collections.max(list, new Comparator<String>() {
			public int compare(String s1, String s2) {
				if (s1.length() > s2.length()) {
					return 1;
				} else {
					return 0;
				}
			}
		});
		// lambda表达式
//		return Collections.max(list, (s1,s2) -> {
//			if (s1.length() > s2.length()) {
//				return 1;
//			} else {
//				return 0;
//			}
//		});
	}
	
	// 遍历List中的元素并输出
	public <T> void pringList(List<T> list) {
		for(T element : list) {
			System.out.print(element+" ");
		}
		System.out.println();
	}
	
	public void printArray(boolean[][] array) {
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				System.out.print(array[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("请输入你想要输入的字符串：");
		String str = sc.nextLine();
		sc.close();
		Main m = new Main();
		System.out.println(m.longestPalindrome(str));
	}
}
